package leetcode.leetcode_142;
/*
*
* fast 走 a+b+(k)(b+c) 步， slow 走 a+b 步
* so fast - slow = k(b+c)
* a +b =K(b+c)
* so a+b = k(b+c)
* so a+b= kc+kb
* a = c+(k-1)(b+c)
* a-c = (k-1)(b+c)
* so slow 只需要走 c 步就能找到环的入口
* if k = 1, a = c
*
* */



class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head ;
        ListNode fast = head ;
        while(fast!=null &&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast){
                while(slow!=head){
                    slow = slow.next;
                    head = head.next;
                }
                return slow;

            }
        }
        return null;
    }
}